class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

/**
 * LCR 026. 重排链表
 * https://leetcode.cn/problems/LGjMqU/description/
 */

class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;

        //1、找到中间节点
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //2、把后面的节点逆序[slow, end] 头插
        ListNode prev = null, cur, next;
        cur = slow;
        next = cur.next;

        while (cur != null) {
            cur.next = prev;
            prev = cur;
            cur = next;
            if (cur != null) next = cur.next;
        }
        //3、合并两个链表 (合并两个有序链表)
        ListNode ccur1, ccur2, next1, next2;
        ccur1 = head;
        ccur2 = prev;
        next1 = ccur1.next;
        next2 = ccur2.next;

        while (ccur1 != null || ccur2 != null) {
            ccur1.next = ccur2;
            if (ccur2 != null) ccur2.next = next1;

            ccur1 = next1;
            if (next1 != null) next1 = ccur1.next;
            ccur2 = next2;
            if (next2 != null) next2 = ccur2.next;
        }
    }
}